package com.future;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 1305. 两棵二叉搜索树中的所有元素
 *
 * @author weiruibai.vendor
 * Date: 2023/1/3 16:29
 */
public class Solution_1305 {

    private static Solution_1305 instance = new Solution_1305();

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(-1);
        root1.right = new TreeNode(4);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(0);
        root2.right = new TreeNode(3);
        List<Integer> allElements = instance.getAllElements(root1, root2);
        System.out.println(allElements);

    }


    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ans = new ArrayList<>();
        List<Integer> pre1 = mid(root1, new ArrayList<>());
        List<Integer> pre2 = mid(root2, new ArrayList<>());
        int i1 = 0;
        int i2 = 0;
        while (i1 < pre1.size() && i2 < pre2.size()) {
            if (i1 < pre1.size() && pre1.get(i1) <= pre2.get(i2)) {
                ans.add(pre1.get(i1++));
            } else if (i2 < pre2.size()) {
                ans.add(pre2.get(i2++));
            }
        }
        while (i1 < pre1.size()) {
            ans.add(pre1.get(i1++));
        }
        while (i2 < pre2.size()) {
            ans.add(pre2.get(i2++));
        }
        return ans;
    }


    private List<Integer> mid(TreeNode root, List<Integer> res) {
        if (root == null) {
            return res;
        }
        mid(root.left, res);
        res.add(root.val);
        mid(root.right, res);
        return res;
    }

}
